class Solution
{
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>> &graph)
    {
        vector<vector<int>> paths{{0}};
        queue<int> qPathIndex; // path的索引
        qPathIndex.push(0);
        while (!qPathIndex.empty())
        {
            int pathId = qPathIndex.front();
            int endNode = paths[pathId].back();
            qPathIndex.pop();
            for (int nextNode : graph[endNode])
            {
                paths.push_back(paths[pathId]);
                paths.back().push_back(nextNode);
                qPathIndex.push(paths.size() - 1);
            }
        }
        vector<vector<int>> result;
        int n = graph.size();
        for (auto &path : paths)
        {
            if (path.back() == n - 1)
            {
                result.push_back(path);
            }
        }
        return result;
    }
};